package gold.digger;

import gold.utils.InputUtil;

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC1094 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public boolean carPooling(int[][] trips, int capacity) {
            Arrays.sort(trips, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[1] - o2[1];
                }
            });

            PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[2] - o2[2];
                }
            });
            int curSize = 0;
            for (int[] trip : trips) {
                int numPeople = trip[0], startTime = trip[1], endTime = trip[2];
                while (!queue.isEmpty() && queue.peek()[2] <= startTime) {
                    curSize -= queue.peek()[0];
                    queue.poll();
                }
                if (curSize + numPeople > capacity) return false;
                queue.offer(trip);
                curSize += numPeople;
            }

            return true;
        }
    }

    public void run() {
        System.out.println(new Solution().carPooling(InputUtil.toDoubleIntegerArray("[[2,1,5],[3,3,7]]"), 4));
        System.out.println(new Solution().carPooling(InputUtil.toDoubleIntegerArray("[[2,1,5],[3,3,7]]"), 5));
        System.out.println(new Solution().carPooling(InputUtil.toDoubleIntegerArray("[[9,3,4],[9,1,7],[4,2,4],[7,4,5]]"), 23));
    }

    public static void main(String[] args) throws Exception {
        LC1094 an = new LC1094();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
